Cage (graph Theory)

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.

Formally, an is defined to be a graph in which each vertex has exactly neighbors, and in which the shortest cycle has length exactly .
An is an with the smallest possible number of vertices, among all . A is often called a .

It is known that an exists for any combination of and . It follows that all exist.

If a Moore graph exists with degree and girth , it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth must have at least
:$1+r\sum_^(r-1)^i$
vertices, and any cage with even girth must have at least
:$2\sum_^(r-1)^i$
vertices. Any with exactly this many vertices is by definition a Moore graph and therefore automatically a cage.

There may exist multiple cages for a given combination of and . For instance there are three nonisomorphic , each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries–Wong graph. But there is only one : the Balaban 11-cage (with 112 vertices).

Known cages

A 1-regular graph has no cycle, and a connected 2-regular graph has girth equal to its number of vertices, so cages are only of interest for ''r'' ≥ 3. The (''r'',3)-cage is a complete graph ''K''_''r''+1 on ''r''+1 vertices, and the (''r'',4)-cage is a complete bipartite graph ''K''_''r'',''r'' on 2''r'' vertices.

Notable cages include:
* (3,5)-cage: the Petersen graph, 10 vertices
* (3,6)-cage: the Heawood graph, 14 vertices
* (3,7)-cage: the McGee graph, 24 vertices
* (3,8)-cage: the Tutte–Coxeter graph, 30 vertices
* (3,10)-cage: the Balaban 10-cage, 70 vertices
* (3,11)-cage: the Balaban 11-cage, 112 vertices
* (4,5)-cage: the Robertson graph, 19 vertices
* (7,5)-cage: The Hoffman–Singleton graph, 50 vertices.
* When ''r'' − 1 is a prime power, the (''r'',6) cages are the incidence graphs of projective planes.
* When ''r'' − 1 is a prime power, the (''r'',8) and (''r'',12) cages are generalized polygons.

The numbers of vertices in the known (''r'',''g'') cages, for values of ''r'' > 2 and ''g'' > 2, other than projective planes and generalized polygons, are:

Asymptotics

For large values of ''g'', the Moore bound implies that the number ''n'' of vertices must grow at least singly exponentially as a function of ''g''. Equivalently, ''g'' can be at most proportional to the logarithm of ''n''. More precisely,
:$g\le 2\log_ n + O(1).$
It is believed that this bound is tight or close to tight . The best known lower bounds on ''g'' are also logarithmic, but with a smaller constant factor (implying that ''n'' grows singly exponentially but at a higher rate than the Moore bound). Specifically, the construction of Ramanujan graphs defined by satisfy the bound
:$g\ge \frac\log_ n + O(1).$

This bound was improved slightly by .

It is unlikely that these graphs are themselves cages, but their existence gives an upper bound to the number of vertices needed in a cage.

References

*.
*.
*.
*.
*.
*.
*.
*.
*.

External links

* Brouwer, Andries E.br>Cages
* Royle, Gordon

an

*{{mathworld , title = Cage Graph , urlname = CageGraph

Graph families
Regular graphs